// 328. 奇偶链表

// 给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别分组，
// 保持它们原有的相对顺序，然后把偶数索引节点分组连接到奇数索引节点分组之后，返回重新排序的链表。

struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *oddEvenList(struct ListNode *head)
{
    if (!head || !head->next)
        return head;

    struct ListNode *odd = head;        // 奇数索引节点的头指针
    struct ListNode *even = head->next; // 偶数索引节点的头指针
    struct ListNode *evenHead = even;   // 保存偶数索引节点的头指针

    // 遍历链表，将奇偶数节点分开
    while (even && even->next)
    {
        odd->next = even->next; // 奇数节点的下一个指向偶数节点的下一个（即下一个奇数节点）
        odd = odd->next;        // 移动奇数节点指针
        even->next = odd->next; // 偶数节点的下一个指向当前奇数节点的下一个（即下一个偶数节点）
        even = even->next;      // 移动偶数节点指针
    }

    odd->next = evenHead; // 将奇数链表的尾部连接到偶数链表的头部
    return head;
}